package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.ArrayList;

/**
 * Created by Administrator on 2017/4/13.
 */
public class GetLeastNumbers_Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if (input == null || input.length == 0 || k > input.length) return result;
        k--;
        int start = 0, end = input.length -1;
        int position = part(input, start, end);
        while (k != position) {
            if (k < position) {
                end = position -1;
                position = part(input, start, end);
            } else {
                start = position +1;
                position = part(input, start, end);
            }
        }
        for (int i = 0; i <= k; i++) {
            result.add(input[i]);
        }
        return result;
    }

    private int part(int[] input, int low, int high) {
        int temp = input[low];
        int j = low;
        for (int i = low+1; i <= high ; i++) {
            if (input[i] < temp) {
                j++;
                if (i!=j){
                    int i1 = input[i];
                    input[i] = input[j];
                    input[j] = i1;
                }
            }
        }
        int i1 = input[low];
        input[low] = input[j];
        input[j] = i1;
        return j;
    }

    public static void main(String[] args) {
        GetLeastNumbers_Solution getLeastNumbers_solution = new GetLeastNumbers_Solution();
        ArrayList<Integer> integers = getLeastNumbers_solution.GetLeastNumbers_Solution(new int[]{4,5,1,6,2,7,3,8}, 6);
        for (Integer integer : integers) {
            System.out.print(integer + "\t");
        }
    }
}
